3.13.6. Код Хэмминга.

         Допустим, что необходимо закодировать текст записанный на некотором языке с числом букв в алфавите n = 2^m (m - целое число), а появление в тексте букв алфавита равновероятно и не зависит от того, какие буквы им предшествовали. Тогда будем иметь p(i = p(j) = 1/n; H = Log₂ = m. Согласно условию задачи достичь оптимального кодирования можно простым методом кодирования, а именно побуквенным кодированием с постоянной длиной (1 = m) кодовых наборов. При этом, однако, исключается возможность обнаруживать, а тем более исправлять ошибки. Чтобы такая возможность появилась, необходимо отказаться от оптимальности кода и добавить несколько дополнительных двоичных символов на букву, т.е. ввести некоторую избыточность, которая поможет обнаружить или исправить ошибки. Если обозначить необходимое число дополнительно вводимых двоичных символов на одну букву через х, то длина кодового набора станет равной 1 = m + х. Примем, что в результате помех (случайных или преднамеренных) лишь один или вовсе никакой из m + x двоичных символов может превратиться из единицы в нуль или, наоборот, из нуля в единицу. Далее примем, что 1 + m + x событий, заключающиеся в том, что ошибка вообще не произойдет, будет на уровне первого, второго, .... (m + х)-го символа кодового набора, равновероятны. Энтропию угадывания того, какое именно из этих 1 + m + x событий будет иметь место, в силу равновероятности этих событий, можно определить по формуле Н = Log₂(1 + m + x) бит. Таким образом, для обнаружения самого факта наличия одиночной ошибки и установления ее позиции необходимо заполучить информацию в количестве не менее Н = Log₂(l + m + х) бит. Источником такой информации может служить лишь дополнительно введенные х двоичные символы, так как остальные m символов из-за оптимальности кодирования описывают сам текст. Заметим, что х двоичных символов в лучшем случае могут содержать информацию в количестве х бит. Поэтому при конструировании кода, обнаруживающего и исправляющего одиночную ошибку, необходимо выполнение неравенства

         Р. Хэмминг предложил конкретный код, который обнаруживает и исправляет одиночные ошибки при минимально возможном числе дополнительно вводимых двоичных символов, т.е. при знаке равенства в (3.9). Предположим, что у этого кода m = 4, а из рис.3.27 в таком случае следует, что допустимое значение х равно трем, т.е. при числе основных (информационных) двоичных символов m = 4, число дополнительно введенных, т.е. контрольных символов должно быть не менее трех.

Рис. 3.27. Зависимость нижней границы допустимых значений x от m (сплошная линия) и зависимость относительной избыточности от m (пунктирная линия).

Примем, что удалось сконструировать такой код с тремя дополнительными символами, при котором каждый из дополнительно введенных трех символов дает нам максимально возможное количество информации, т.е. по одному биту. Тогда в расширенном кодовом наборе окажутся семь двоичных символов:

Символы В1 - В4 несут собственно информацию и только символов В5 - В7 предназначены для обнаружения и исправления ошибок. Поэтому их значения можно выразить через информационные символы произвольными тремя функциями от аргументов В1 - В4:

такими, чтобы в последующем с помощью трех других функций от аргументов

определить значения e_o, e_i, e₂ содержащие информацию о том, произошла ли ошибка вообще и если да, то на уровне какого именно из семи символов. Очевидно, имеется множество различных вариантов при выборе функций (3.11) - (3.13). Р. Хэмминг поставил перед собой задачу выбора именно такой совокупности функций (3.11) - (3.13), чтобы набор значений е….. оказался двоичной записью позиции, где произошла ошибка. В случае же, когда ошибка не имела места, набор е…… должен указать на нулевую позицию, т.е. на несуществующий символ ВО. Из двоичной записи этих позиций

видно, что значение е…. "несет ответственность" за позиции В1, ВЗ, В5 и В7 и поэтому в качестве функции (3.14) берется зависимость е₀ = В1+ВЗ+В5+В7 mod 2. (3.14, а).
        Аналогично, обращая внимание на то, что значения e_i и е₂ отвечают за соответственно В2 ВЗ В6 В7 , В4 В5 В6 В7, получим

        Систему (3.14, а) - (3.16, а) можно рассматривать как развернутую запись матричного уравнения

Операция сложения во всех трех уравнениях (3.14, а) - (3.16, а) осуществляется по модулю два. Подставляя в систему уравнении (3.14, а) - (3.16, а) e_o = e_i = e₂= 0, получим систему из трех уравнений

Приняв в качестве неизвестных величины В5, В6 и В7 получим систему из трех уравнений с тремя неизвестными:

Эта система эквивалентна одному матричному уравнению

        Столбцы этих матриц суть двоичные записи номеров соответственно контрольных и информационных разрядов. Решение системы (3.14 в) - (3.16 в), или. что то же самое, матричного уравнения (3.17) относительно В5, В6, В7 приводит к конкретным выражениям для функций (3.11) - (3.13):

        Р. Хэмминг в качестве контрольного берет не набор символов B(m+l), B(m+2), ... B(m+x), а набор символов, индексы которых представляют целые степени двойки. В случае, когда число контрольных символов равно трем, эти индексы равны 2⁰ =1, 2¹ = 2 и 2² = 4, т.е. речь идет о наборе символов Bl B2 B4, относительно которых решение системы (3.14 б) - (3.16 б) существенно упрощается:

        Это вполне объяснимо, так как вместо (3.17) используем матричное уравнение

        При указанной рекомендации Р. Хэмминга контрольная матрица всегда (независимо от m и х) оказывается равной единице. Далее рассмотрим в качестве контрольных набор символов В5В6В7, а в качестве информационных - Bl B2B3B4. Для примера возмем набор информационных символов В1В2ВЗВ4 = 1011 и с помощью зависимостей (3.11а) - (3.13а) определим набор контрольных (дополнительно введенных, избыточных) символов В5В6В7 = 010. Пусть ошибка произошла на уровне символа В5, т.е. вместо истинного расширенного кодового набора 1011 (0)10 получен код 1011 (1)10. Тогда с помощью зависимостей (3.14а) - (3.16а) найдем

        Набор значений e…e…e…. = 101 является двоичной записью числа "пять", т.е. указывает именно на пятую позицию (на символ В5), где, собственно, и произошла ошибка. Приведенная схема Р. Хэмминга по конструированию кода, обнаруживающего и исправляющего одиночную ошибку, универсальна, и аналогичный код может быть построен для произвольной пары значений m и х, удовлетворяющих уравнению

        Заметим также, что вовсе не обязательно, чтобы набор из m информационных символов представлял собой код какой-то определенной буквы, как это имело место в только что рассмотренном примере. На практике сначала можно осуществить оптимальное (или близкое к оптимальному) кодирование текста. Затем уже закодированный текст можно делить на блоки по m двоичных символов в каждом, причем из возможных значений m = 2^х - х - 1 (х = 3, 4,...) его конкретное значение следует выбирать исходя из эксплуатационной необходимости. При прочих равных условиях значение m должно быть тем меньшим, чем больше значимость информации и чем больше уровень помех. После выбора конкретного значения m каждый блок из m информационных символов следует наращивать х = х (m) контрольными символами, предназначенными для обнаружения и исправления одиночных ошибок в рамках данного блока.
         Теперь обсудим, почему Р. Хэмминг в качестве контрольных берет символы, индексы которых равны целым степеням двойки, т.е. 1, 2, 4, 8, 16, .... Во-первых, как уже об этом говорилось выше, при таком выборе контрольная матрица всегда оказывается равной единице, т.е. фактически снимается вопрос решения системы (3.14 б) - (3.16 б) относительно контрольных символов, так как ее "решение" сводится к простому переписыванию соответствующих уравнений. Но это не главное, так как систему (3.14 б) - (3.16 б) приходится решать только один раз и далее при каждом акте кодирования пользуются лишь системой (3.11 а) - (3.13 а) - решением системы (3.14 б) - (3.16 б) относительно контрольных символов. При реализации процедур кодирования и декодирования на ЭВМ сам факт, что контрольные символы разобщены (не следуют подряд друг за другом), создает определенные неудобства при каждом акте кодирования и декодирования. Естественно поэтому желание выбрать контрольные символы таковыми, чтобы они следовали подряд друг за другом, пусть даже ценою того, чтобы один раз приходится решать систему (3.14 б) - (3.16 б). Именно так поступали, когда вопреки рекомендациям Р. Хэмминга брали в качестве контрольных символы В1,В2 и В4 вместо В5, В6 и В7, что вынуждало решить систему (3.14 в) - (3.16 в) относительно переменных В5, В6 и В7, но зато при каждом акте кодирования и декодирования могли оперировать "пачками" контрольных символов, а не "выковыривать" их среди информационных символов.
         При любом числе информационных символов нельзя поступать аналогичным образом, если по-прежнему хотим, чтобы двоичный набор символов e_x - i, ………… указывал на адрес ошибки. Связанно это с тем, что когда число контрольных символов больше трех, нельзя брать в качестве контрольных последние х символов, так как при этом контрольная матрица непременно оказалась бы вырожденной, т.е. значение ее детерминанта оказалась бы равным нулю. Более того, даже в рассмотренном случае, когда число контрольных символов равно трем, нельзя в качестве контрольных брать, например, первые три символа. Во всех этих случаях определители контрольных матриц ( столбцы этой матрицы суть двоичные записи номеров выбранных нами контрольных символов) оказываются равными нулю. Например, выберем в качестве контрольных не пачку символов В5. В6, В7, а символы Bl, B2, ВЗ. Тогда пришлось бы иметь дело с квадратной матрицей третьего порядка, столбцы которой являются двоичными формами записи чисел 1, 2 и 3:

         Равенство нулю детерминанта этой матрицы свидетельствует о том, что систему (3.14 б) - (3.16 б) нельзя решить относительно переменных Bl, B2, ВЗ. Таким образом, при выборе среди m + х символов х контрольных следует заботиться о том, чтобы определитель контрольной матрицы порядка х, столбцы которой представляют собой двоичные записи номеров выбранных символов, не оказался равным нулю. Для того чтобы исключить это, Р. Хэмминг рекомендует в качестве контрольных брать символы с индексами I, 2, 4, 8 и т.д. При таком выборе контрольных символов всегда (независимо от их числа) будет иметь место единичная матрица. Кроме зависимости (3.10) на рис.3.27 приведена также зависимость относительной избыточности от m. Легко заметить, что с увеличением m требуемый процент избыточности для обнаружения и исправления одиночной ошибки резко уменьшается. Столь неестественный результат является следствием искусственного, далекого от реальности допущения, что в рамках каждого кодового набора независимо от его длины m + x может произойти не более одной ошибки. Если же допустить возможность двух и более ошибок, то задача их обнаружения, и тем более исправления усложняется. Подобрать для этих случаев коды, подобные коду Р. Хэмминга для одиночной ошибки, пока не удается.